package gold.digger;

import gold.utils.InputUtil;

import java.util.*;

/**
 * Created by fanzhenyu02 on 2021/12/10.
 * common problem solver template.
 */
public class LC1278 {
    public long startExecuteTime = System.currentTimeMillis();


    class Solution {

        Map<String, Integer> memo = new HashMap<>();
        Map<String, Integer> lenMemo = new HashMap<>();

        public int palindromePartition(String s, int k) {
            return dfs(s, 0, k);
        }

        public int dfs(String s, int i, int k) {
            if (k == 1) return getCurMinModifyCnt(s, i, s.length() - 1);
            if (s.length() - i < k) return Integer.MAX_VALUE;
            String key = i + "_" + k;
            if (memo.containsKey(key)) return memo.get(key);

            int curStartMinModify = Integer.MAX_VALUE;
            for (int j = i; j <= s.length() - k; j++) {
                int curJModifyCnt = getCurMinModifyCnt(s, i, j);
                int nextPartMinModifyCnt = dfs(s, j + 1, k - 1);
                curStartMinModify = Math.min(curStartMinModify, curJModifyCnt + nextPartMinModifyCnt);
            }

            memo.put(key, curStartMinModify);
            return curStartMinModify;
        }

        public int getCurMinModifyCnt(String s, int i, int j) {
            String key = i + "_" + j;
            if (lenMemo.containsKey(key)) return lenMemo.get(key);
            int cnt = 0;
            while (i < j) {
                if (s.charAt(i++) != s.charAt(j--)) cnt++;
            }

            lenMemo.put(key, cnt);
            return cnt;
        }
    }

    public void run() {
//        System.out.println(new Solution().getCurMinModifyCnt("abcd", 0, 3));
        System.out.println(new Solution().palindromePartition("abc", 2));
        System.out.println(new Solution().palindromePartition("aabbc", 3));
        System.out.println(new Solution().palindromePartition("leetcode", 8));
    }

    public static void main(String[] args) throws Exception {
        LC1278 an = new LC1278();
        an.run();

        System.out.println("\ncurrent solution total execute time: " + (System.currentTimeMillis() - an.startExecuteTime) + " ms.");
    }
}
